//1143. 最长公共子序列

//给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
//一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
//例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
//两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

//class Solution {
//public:
//    int longestCommonSubsequence(string s, string t) {
//        int n = s.length(), m = t.length();
//        vector f(n + 1, vector<int>(m + 1));
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < m; j++) {
//                f[i + 1][j + 1] = s[i] == t[j] ? f[i][j] + 1 : max(f[i][j + 1], f[i + 1][j]);
//            }
//        }
//        return f[n][m];
//    }
//};

//583. 两个字符串的删除操作

//给定两个单词 word1 和 word2 ，返回使得 word1 和  word2 相同所需的最小步数。
//每步 可以删除任意一个字符串中的一个字符。

//class Solution {
//public:
//    int minDistance(string word1, string word2) {
//        int m = word1.size();
//        int n = word2.size();
//        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
//
//        for (int i = 1; i <= m; i++) {
//            char c1 = word1[i - 1];
//            for (int j = 1; j <= n; j++) {
//                char c2 = word2[j - 1];
//                if (c1 == c2) {
//                    dp[i][j] = dp[i - 1][j - 1] + 1;
//                }
//                else {
//                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
//                }
//            }
//        }
//
//        int lcs = dp[m][n];
//        return m - lcs + n - lcs;
//    }
//};

//712. 两个字符串的最小ASCII删除和

//给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。

//class Solution {
//public:
//    int minimumDeleteSum(string s1, string s2) {
//        int m = s1.size();
//        int n = s2.size();
//        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
//
//        for (int i = 1; i <= m; ++i) {
//            dp[i][0] = dp[i - 1][0] + s1[i - 1];
//        }
//        for (int j = 1; j <= n; ++j) {
//            dp[0][j] = dp[0][j - 1] + s2[j - 1];
//        }
//        for (int i = 1; i <= m; i++) {
//            char c1 = s1[i - 1];
//            for (int j = 1; j <= n; j++) {
//                char c2 = s2[j - 1];
//                if (c1 == c2) {
//                    dp[i][j] = dp[i - 1][j - 1];
//                }
//                else {
//                    dp[i][j] = min(dp[i - 1][j] + s1[i - 1], dp[i][j - 1] + s2[j - 1]);
//                }
//            }
//        }
//
//        return dp[m][n];
//    }
//};

//72. 编辑距离

//给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。
//你可以对一个单词进行如下三种操作：
//插入一个字符
//删除一个字符
//替换一个字符

//class Solution {
//public:
//    int minDistance(string word1, string word2) {
//        int n = word1.length();
//        int m = word2.length();
//
//        if (n * m == 0) return n + m;
//        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
//        for (int i = 0; i < n + 1; i++) {
//            dp[i][0] = i;
//        }
//        for (int j = 0; j < m + 1; j++) {
//            dp[0][j] = j;
//        }
//        for (int i = 1; i < n + 1; i++) {
//            for (int j = 1; j < m + 1; j++) {
//                int left = dp[i - 1][j] + 1;
//                int down = dp[i][j - 1] + 1;
//                int left_down = dp[i - 1][j - 1];
//                if (word1[i - 1] != word2[j - 1]) left_down += 1;
//                dp[i][j] = min(left, min(down, left_down));
//
//            }
//        }
//        return dp[n][m];
//    }
//};

//1035. 不相交的线

//在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
//现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足：
//nums1[i] == nums2[j]
//且绘制的直线不与任何其他连线（非水平线）相交。
//请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。
//以这种方法绘制线条，并返回可以绘制的最大连线数。

//class Solution {
//public:
//    int maxUncrossedLines(vector<int>& s, vector<int>& t) {
//        int n = s.size(), m = t.size();
//        vector<vector<int>> f(n + 1, vector<int>(m + 1));
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < m; j++) {
//                f[i + 1][j + 1] = s[i] == t[j] ? f[i][j] + 1 : max(f[i][j + 1], f[i + 1][j]);
//            }
//        }
//        return f[n][m];
//    }
//};

//1458. 两个子序列的最大点积

//给你两个数组 nums1 和 nums2 。
//请你返回 nums1 和 nums2 中两个长度相同的 非空 子序列的最大点积。
//数组的非空子序列是通过删除原数组中某些元素（可能一个也不删除）后剩余数字组成的序列，但不能改变数字间相对顺序。比方说，[2, 3, 5] 是[1, 2, 3, 4, 5] 的一个子序列而[1, 5, 3] 不是。

//class Solution {
//public:
//    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
//        int m = nums1.size();
//        int n = nums2.size();
//        vector<vector<int>> f(m, vector<int>(n));
//
//        for (int i = 0; i < m; ++i) {
//            for (int j = 0; j < n; ++j) {
//                int xij = nums1[i] * nums2[j];
//                f[i][j] = xij;
//                if (i > 0) {
//                    f[i][j] = max(f[i][j], f[i - 1][j]);
//                }
//                if (j > 0) {
//                    f[i][j] = max(f[i][j], f[i][j - 1]);
//                }
//                if (i > 0 && j > 0) {
//                    f[i][j] = max(f[i][j], f[i - 1][j - 1] + xij);
//                }
//            }
//        }
//
//        return f[m - 1][n - 1];
//    }
//};

//718. 最长重复子数组

//给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

//class Solution {
//public:
//    int findLength(vector<int>& nums1, vector<int>& nums2) {
//        int n = nums1.size(), m = nums2.size(), ans = 0;
//        vector f(n + 1, vector<int>(m + 1));
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < m; j++) {
//                if (nums1[i] == nums2[j]) {
//                    f[i + 1][j + 1] = f[i][j] + 1;
//                    ans = max(ans, f[i + 1][j + 1]);
//                }
//            }
//        }
//        return ans;
//    }
//};

//3290. 最高乘法得分

//给你一个大小为 4 的整数数组 a 和一个大小 至少为 4 的整数数组 b。
//你需要从数组 b 中选择四个下标 i0, i1, i2, 和 i3，并满足 i0 < i1 < i2 < i3。你的得分将是 a[0] * b[i0] + a[1] * b[i1] + a[2] * b[i2] + a[3] * b[i3] 的值。
//返回你能够获得的 最大 得分。

//class Solution {
//public:
//    long long maxScore(vector<int>& a, vector<int>& b) {
//        int n = b.size();
//        vector<array<long long, 5>> f(n + 1);
//        for (int j = 1; j < 5; j++) {
//            f[0][j] = LLONG_MIN / 2;
//        }
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < 4; j++) {
//                f[i + 1][j + 1] = max(f[i][j + 1], f[i][j] + (long long)a[j] * b[i]);
//            }
//        }
//        return f[n][4];
//    }
//};

//115. 不同的子序列

//给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。
//测试用例保证结果在 32 位有符号整数范围内。

//class Solution {
//public:
//    int numDistinct(string s, string t) {
//        int n = s.size(), m = t.size();
//        if (n < m) {
//            return 0;
//        }
//
//        vector f(n + 1, vector<unsigned>(m + 1));
//        f[0][0] = 1;
//        for (int i = 0; i < n; i++) {
//            f[i + 1][0] = 1;
//            for (int j = max(m - n + i, 0); j < min(i + 1, m); j++) {
//                f[i + 1][j + 1] = f[i][j + 1];
//                if (s[i] == t[j]) {
//                    f[i + 1][j + 1] += f[i][j];
//                }
//            }
//        }
//        return f[n][m];
//    }
//};

//3628. 插入一个字母的最大子序列数

//给你一个由大写英文字母组成的字符串 s。
//你可以在字符串的 任意 位置（包括字符串的开头或结尾）最多插入一个 大写英文字母。
//返回在 最多插入一个字母 后，字符串中可以形成的 "LCT" 子序列的 最大 数量。
//子序列 是从另一个字符串中删除某些字符（可以不删除）且不改变剩余字符顺序后得到的一个 非空 字符串。

//class Solution {
//public:
//    long long numOfSubsequences(string s) {
//        int t = ranges::count(s, 'T');
//        long long l = 0, lc = 0, lct = 0, c = 0, ct = 0, lt = 0;
//        for (char b : s) {
//            if (b == 'L') {
//                l++;
//            }
//            else if (b == 'C') {
//                lc += l;
//                c++;
//            }
//            else if (b == 'T') {
//                lct += lc;
//                ct += c;
//                t--;
//            }
//            lt = max(lt, l * t);
//        }
//        return lct + max({ ct, lc, lt });
//    }
//};

//3316. 从原字符串里进行删除操作的最多次数

//给你一个长度为 n 的字符串 source ，一个字符串 pattern 且它是 source 的 子序列 ，和一个 有序 整数数组 targetIndices ，整数数组中的元素是[0, n - 1] 中 互不相同 的数字。
//定义一次 操作 为删除 source 中下标在 idx 的一个字符，且需要满足：
//idx 是 targetIndices 中的一个元素。
//删除字符后，pattern 仍然是 source 的一个 子序列 。
//执行操作后 不会 改变字符在 source 中的下标位置。比方说，如果从 "acb" 中删除 'c' ，下标为 2 的字符仍然是 'b' 。
//请你返回 最多 可以进行多少次删除操作。
//子序列指的是在原字符串里删除若干个（也可以不删除）字符后，不改变顺序地连接剩余字符得到的字符串。

//class Solution {
//public:
//    int maxRemovals(string source, string pattern, vector<int>& targetIndices) {
//        unordered_set<int> st(targetIndices.begin(), targetIndices.end());
//        int n = source.length(), m = pattern.length();
//        vector<vector<int>> f(n + 1, vector<int>(m + 1, INT_MIN));
//        f[0][0] = 0;
//        for (int i = 0; i < n; i++) {
//            int is_del = st.count(i);
//            f[i + 1][0] = f[i][0] + is_del;
//            for (int j = 0; j < min(i + 1, m); j++) {
//                f[i + 1][j + 1] = f[i][j + 1] + is_del;
//                if (source[i] == pattern[j]) {
//                    f[i + 1][j + 1] = max(f[i + 1][j + 1], f[i][j]);
//                }
//            }
//        }
//        return f[n][m];
//    }
//};

//1639. 通过给定词典构造目标字符串的方案数

//给你一个字符串列表 words 和一个目标字符串 target 。words 中所有字符串都 长度相同  。
//你的目标是使用给定的 words 字符串列表按照下述规则构造 target ：
//从左到右依次构造 target 的每一个字符。
//为了得到 target 第 i 个字符（下标从 0 开始），当 target[i] = words[j][k] 时，你可以使用 words 列表中第 j 个字符串的第 k 个字符。
//一旦你使用了 words 中第 j 个字符串的第 k 个字符，你不能再使用 words 字符串列表中任意单词的第 x 个字符（x <= k）。也就是说，所有单词下标小于等于 k 的字符都不能再被使用。
//请你重复此过程直到得到目标字符串 target 。
//请注意， 在构造目标字符串的过程中，你可以按照上述规定使用 words 列表中 同一个字符串 的 多个字符 。
//请你返回使用 words 构造 target 的方案数。由于答案可能会很大，请对 109 + 7 取余 后返回。
//（译者注：此题目求的是有多少个不同的 k 序列，详情请见示例。）

//class Solution {
//public:
//    const int mod = 1e9 + 7;
//    int numWays(vector<string>& words, string target) {
//        int n = words[0].size();
//        vector<array<int, 26>> cnt(n);
//        for (const auto& s : words) {
//            for (int i = 0; i < n; i++) {
//                cnt[i][s[i] - 'a']++;
//            }
//        }
//
//        int m = target.size();
//        vector<vector<long>> dp(n, vector<long>(m, -1));
//        auto dfs = [&](this auto&& dfs, int i, int j) -> long {
//            if (j == m) {
//                return 1;
//            }
//            if (n - i < m - j) {
//                return 0;
//            }
//            if (dp[i][j] != -1) {
//                return dp[i][j];
//            }
//
//            long val = cnt[i][target[j] - 'a'] * dfs(i + 1, j + 1);
//            val += dfs(i + 1, j);
//            val %= mod;
//            return dp[i][j] = val;
//            };
//        return dfs(0, 0);
//    }
//};

//97. 交错字符串

//给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。
//两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：
//s = s1 + s2 + ... + sn
//t = t1 + t2 + ... + tm
//| n - m| <= 1
//交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...
//注意：a + b 意味着字符串 a 和 b 连接。

//class Solution {
//public:
//    bool isInterleave(string s1, string s2, string s3) {
//        int n = s1.size(), m = s2.size();
//        if (n + m != s3.size()) {
//            return false;
//        }
//
//        vector<vector<int8_t>> f(n + 1, vector<int8_t>(m + 1));
//        f[0][0] = true;
//        for (int j = 0; j < m; j++) {
//            f[0][j + 1] = s2[j] == s3[j] && f[0][j];
//        }
//        for (int i = 0; i < n; i++) {
//            f[i + 1][0] = s1[i] == s3[i] && f[i][0];
//            for (int j = 0; j < m; j++) {
//                f[i + 1][j + 1] = s1[i] == s3[i + j + 1] && f[i][j + 1] || s2[j] == s3[i + j + 1] && f[i + 1][j];
//            }
//        }
//        return f[n][m];
//    }
//};

//1092. 最短公共超序列

//给你两个字符串 str1 和 str2，返回同时以 str1 和 str2 作为 子序列 的最短字符串。如果答案不止一个，则可以返回满足条件的 任意一个 答案。
//如果从字符串 t 中删除一些字符（也可能不删除），可以得到字符串 s ，那么 s 就是 t 的一个子序列

//class Solution {
//public:
//    string shortestCommonSupersequence(string& s, string& t) {
//        // f[i+1][j+1] 表示 s 的前缀 [0,i] 和 t 的前缀 [0,j]
//        // 的最短公共超序列的长度
//        int n = s.size(), m = t.size(), f[n + 1][m + 1];
//        for (int j = 0; j <= m; ++j) { // 递归边界
//            f[0][j] = j;
//        }
//        for (int i = 1; i <= n; ++i) { // 递归边界
//            f[i][0] = i;
//        }
//        for (int i = 0; i < n; ++i) {
//            for (int j = 0; j < m; ++j) {
//                if (s[i] == t[j]) { // 最短公共超序列一定包含 s[i]
//                    f[i + 1][j + 1] = f[i][j] + 1;
//                }
//                else { // 取更短的组成答案
//                    f[i + 1][j + 1] = min(f[i][j + 1], f[i + 1][j]) + 1;
//                }
//            }
//        }
//        string ans;
//        int i = n - 1, j = m - 1;
//        while (i >= 0 && j >= 0) {
//            if (s[i] == t[j]) { // 公共超序列一定包含 s[i]
//                ans += s[i];
//                --i;
//                --j;
//            }
//            else if (f[i + 1][j + 1] == f[i][j + 1] + 1) {
//                ans += s[i--];
//            }
//            else {
//                ans += t[j--];
//            }
//        }
//        reverse(ans.begin(), ans.end());
//        // 补上前面的递归边界
//        return s.substr(0, i + 1) + t.substr(0, j + 1) + ans;
//    }
//};

//44. 通配符匹配

//给你一个输入字符串(s) 和一个字符模式(p) ，请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：
//'?' 可以匹配任何单个字符。
//'*' 可以匹配任意字符序列（包括空字符序列）。
//判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。

//class Solution {
//public:
//    bool isMatch(string s, string p) {
//        int m = s.size();
//        int n = p.size();
//        vector<vector<int8_t>> dp(m + 1, vector<int8_t>(n + 1));
//        dp[0][0] = true;
//        for (int i = 1; i <= n; ++i) {
//            if (p[i - 1] == '*') {
//                dp[0][i] = true;
//            }
//            else {
//                break;
//            }
//        }
//        for (int i = 1; i <= m; ++i) {
//            for (int j = 1; j <= n; ++j) {
//                if (p[j - 1] == '*') {
//                    dp[i][j] = dp[i][j - 1] | dp[i - 1][j];
//                }
//                else if (p[j - 1] == '?' || s[i - 1] == p[j - 1]) {
//                    dp[i][j] = dp[i - 1][j - 1];
//                }
//            }
//        }
//        return dp[m][n];
//    }
//};

//10. 正则表达式匹配

//给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
//'.' 匹配任意单个字符
//'*' 匹配零个或多个前面的那一个元素
//所谓匹配，是要涵盖 整个 字符串 s 的，而不是部分字符串。

//class Solution {
//public:
//    bool isMatch(string s, string p) {
//        int m = s.size();
//        int n = p.size();
//
//        auto matches = [&](int i, int j) {
//            if (i == 0) {
//                return false;
//            }
//            if (p[j - 1] == '.') {
//                return true;
//            }
//            return s[i - 1] == p[j - 1];
//            };
//
//        vector<vector<int>> f(m + 1, vector<int>(n + 1));
//        f[0][0] = true;
//        for (int i = 0; i <= m; ++i) {
//            for (int j = 1; j <= n; ++j) {
//                if (p[j - 1] == '*') {
//                    f[i][j] |= f[i][j - 2];
//                    if (matches(i, j - 1)) {
//                        f[i][j] |= f[i - 1][j];
//                    }
//                }
//                else {
//                    if (matches(i, j)) {
//                        f[i][j] |= f[i - 1][j - 1];
//                    }
//                }
//            }
//        }
//        return f[m][n];
//    }
//};

//300. 最长递增子序列

//给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
//子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3, 6, 2, 7] 是数组[0, 3, 1, 6, 2, 2, 7] 的子序列。

//class Solution {
//public:
//    int lengthOfLIS(vector<int>& nums) {
//        int n = nums.size();
//        vector<int> f(n);
//        for (int i = 0; i < n; i++) {
//            f[i] = 0;
//            for (int j = 0; j < i; j++) {
//                if (nums[j] < nums[i]) {
//                    f[i] = max(f[i], f[j]);
//                }
//            }
//            f[i]++;
//        }
//        return ranges::max(f);
//    }
//};

//2826. 将三个组排序

//给你一个整数数组 nums 。nums 的每个元素是 1，2 或 3。在每次操作中，你可以删除 nums 中的一个元素。返回使 nums 成为 非递减 顺序所需操作数的 最小值。

//class Solution {
//public:
//    int minimumOperations(vector<int>& nums) {
//        int n = nums.size();
//        vector<array<int, 4>> f(n + 1);
//        for (int i = 0; i < n; i++) {
//            int x = nums[i];
//            for (int j = 1; j <= 3; j++) {
//                if (j < x) {
//                    f[i + 1][j] = f[i][j];
//                }
//                else {
//                    f[i + 1][j] = max(f[i][j], f[i][x] + 1);
//                }
//            }
//        }
//        return n - f[n][3];
//    }
//};

//1671. 得到山形数组的最少删除次数

//我们定义 arr 是 山形数组 当且仅当它满足：
//arr.length >= 3
//存在某个下标 i （从 0 开始） 满足 0 < i < arr.length - 1 且：
//arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
//arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
//给你整数数组 nums​ ，请你返回将 nums 变成 山形状数组 的​ 最少 删除次数。

//class Solution {
//public:
//    int minimumMountainRemovals(vector<int>& nums) {
//        int n = nums.size();
//        vector<int> suf(n), g;
//        for (int i = n - 1; i; i--) {
//            int x = nums[i];
//            auto it = lower_bound(g.begin(), g.end(), x);
//            suf[i] = it - g.begin() + 1; // 从 nums[i] 开始的最长严格递减子序列的长度
//            if (it == g.end()) {
//                g.push_back(x);
//            }
//            else {
//                *it = x;
//            }
//        }
//
//        int mx = 0;
//        g.clear();
//        for (int i = 0; i < n - 1; i++) {
//            int x = nums[i];
//            auto it = lower_bound(g.begin(), g.end(), x);
//            int pre = it - g.begin() + 1; // 在 nums[i] 结束的最长严格递增子序列的长度
//            if (it == g.end()) {
//                g.push_back(x);
//            }
//            else {
//                *it = x;
//            }
//            if (pre >= 2 && suf[i] >= 2) {
//                mx = max(mx, pre + suf[i] - 1); // 减去重复的 nums[i]
//            }
//        }
//        return n - mx;
//    }
//};

//1964. 找出到每个位置为止最长的有效障碍赛跑路线

//你打算构建一些障碍赛跑路线。给你一个 下标从 0 开始 的整数数组 obstacles ，数组长度为 n ，其中 obstacles[i] 表示第 i 个障碍的高度。
//对于每个介于 0 和 n - 1 之间（包含 0 和 n - 1）的下标  i ，在满足下述条件的前提下，请你找出 obstacles 能构成的最长障碍路线的长度：
//你可以选择下标介于 0 到 i 之间（包含 0 和 i）的任意个障碍。
//在这条路线中，必须包含第 i 个障碍。
//你必须按障碍在 obstacles 中的 出现顺序 布置这些障碍。
//除第一个障碍外，路线中每个障碍的高度都必须和前一个障碍 相同 或者 更高 。
//返回长度为 n 的答案数组 ans ，其中 ans[i] 是上面所述的下标 i 对应的最长障碍赛跑路线的长度。

//class Solution {
//public:
//    vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
//        int n = obstacles.size();
//        vector<int> ans;
//        vector<int> g;
//        for (int x : obstacles) {
//            auto it = ranges::upper_bound(g, x);
//            if (it == g.end()) {
//                g.emplace_back(x);
//                ans.emplace_back(g.size());
//            }
//            else {
//                *it = x;
//                ans.emplace_back(it - g.begin() + 1);
//            }
//        }
//        return ans;
//    }
//};

//2111. 使数组 K 递增的最少操作次数

//给你一个下标从 0 开始包含 n 个正整数的数组 arr ，和一个正整数 k 。
//如果对于每个满足 k <= i <= n - 1 的下标 i ，都有 arr[i - k] <= arr[i] ，那么我们称 arr 是 K 递增 的。
//比方说，arr = [4, 1, 5, 2, 6, 2] 对于 k = 2 是 K 递增的，因为：
//arr[0] <= arr[2](4 <= 5)
//arr[1] <= arr[3](1 <= 2)
//arr[2] <= arr[4](5 <= 6)
//arr[3] <= arr[5](2 <= 2)
//但是，相同的数组 arr 对于 k = 1 不是 K 递增的（因为 arr[0] > arr[1]），对于 k = 3 也不是 K 递增的（因为 arr[0] > arr[3] ）。
//每一次 操作 中，你可以选择一个下标 i 并将 arr[i] 改成任意 正整数。
//请你返回对于给定的 k ，使数组变成 K 递增的 最少操作次数 。

//class Solution {
//public:
//    int kIncreasing(vector<int>& arr, int k) {
//        int n = arr.size();
//        int ans = 0;
//        for (int i = 0; i < k; i++) {
//            vector<int> g;
//            int cnt = 0;
//            for (int j = i; j < n; j += k, cnt++) {
//                // 寻找大于x的
//                auto it = ranges::lower_bound(g, arr[j] + 1);
//                if (it == g.end()) {
//                    g.emplace_back(arr[j]); // >x 的 g[j] 不存在
//                }
//                else {
//                    *it = arr[j];
//                }
//            }
//            ans += cnt - g.size();
//        }
//        return ans;
//    }
//};

//354. 俄罗斯套娃信封问题

//给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
//当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
//请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
//注意：不允许旋转信封。

//class Solution {
//public:
//    int maxEnvelopes(vector<vector<int>>& envelopes) {
//        ranges::sort(envelopes, {}, [](auto& e) { return pair(e[0], -e[1]); });
//        vector<int> g;
//        for (auto& e : envelopes) {
//            int h = e[1];
//            auto it = ranges::lower_bound(g, h);
//            if (it != g.end()) {
//                *it = h;
//            }
//            else {
//                g.emplace_back(h);
//            }
//        }
//        return g.size();
//    }
//};

//1626. 无矛盾的最佳球队

//假设你是球队的经理。对于即将到来的锦标赛，你想组合一支总体得分最高的球队。球队的得分是球队中所有球员的分数 总和 。
//然而，球队中的矛盾会限制球员的发挥，所以必须选出一支 没有矛盾 的球队。如果一名年龄较小球员的分数 严格大于 一名年龄较大的球员，则存在矛盾。同龄球员之间不会发生矛盾。
//给你两个列表 scores 和 ages，其中每组 scores[i] 和 ages[i] 表示第 i 名球员的分数和年龄。请你返回 所有可能的无矛盾球队中得分最高那支的分数 。

//class Solution {
//public:
//    int bestTeamScore(vector<int>& scores, vector<int>& ages) {
//        int n = scores.size();
//        vector<pair<int, int>> a(n);
//        for (int i = 0; i < n; ++i)
//            a[i] = { scores[i], ages[i] };
//        ranges::sort(a);
//
//        vector<int> f(n);
//        for (int i = 0; i < n; ++i) {
//            for (int j = 0; j < i; ++j)
//                if (a[j].second <= a[i].second)
//                    f[i] = max(f[i], f[j]);
//            f[i] += a[i].first;
//        }
//        return *ranges::max_element(f);
//    }
//};

//1691. 堆叠长方体的最大高度

//给你 n 个长方体 cuboids ，其中第 i 个长方体的长宽高表示为 cuboids[i] = [widthi, lengthi, heighti]（下标从 0 开始）。请你从 cuboids 选出一个 子集 ，并将它们堆叠起来。
//如果 widthi <= widthj 且 lengthi <= lengthj 且 heighti <= heightj ，你就可以将长方体 i 堆叠在长方体 j 上。你可以通过旋转把长方体的长宽高重新排列，以将它放在另一个长方体上。
//返回 堆叠长方体 cuboids 可以得到的 最大高度 。

//class Solution {
//public:
//    int maxHeight(vector<vector<int>>& cuboids) {
//        for (auto& c : cuboids) {
//            ranges::sort(c);
//        }
//        ranges::sort(cuboids);
//        int n = cuboids.size();
//        vector<int> f(n);
//        for (int i = 0; i < n; ++i) {
//            f[i] = 0;
//            for (int j = 0; j < i; ++j) { // 排序后，cuboids[j][0] <= cuboids[i][0] 恒成立
//                if (cuboids[j][1] <= cuboids[i][1] && cuboids[j][2] <= cuboids[i][2]) {
//                    f[i] = max(f[i], f[j]); // cuboids[j] 可以堆在 cuboids[i] 上
//                }
//            }
//            f[i] += cuboids[i][2];
//        }
//        return *ranges::max_element(f);
//    }
//};

//960. 删列造序 III

//给定由 n 个小写字母字符串组成的数组 strs ，其中每个字符串长度相等。
//选取一个删除索引序列，对于 strs 中的每个字符串，删除对应每个索引处的字符。
//比如，有 strs = ["abcdef", "uvwxyz"] ，删除索引序列{ 0, 2, 3 } ，删除后为["bef", "vyz"] 。
//假设，我们选择了一组删除索引 answer ，那么在执行删除操作之后，最终得到的数组的行中的 每个元素 都是按字典序排列的（即(strs[0][0] <= strs[0][1] <= ... <= strs[0][strs[0].length - 1]) 
//和(strs[1][0] <= strs[1][1] <= ... <= strs[1][strs[1].length - 1]) ，依此类推）。
//请返回 answer.length 的最小可能值 。

//class Solution {
//public:
//    int minDeletionSize(vector<string>& strs) {
//        int n = strs[0].size(), m = strs.size();
//        vector<int> f(n);
//        for (int i = 0; i < n; i++) {
//            f[i] = 0;
//            for (int j = 0; j < i; j++) {
//                int flag = 1;
//                for (int k = 0; k < m; k++) {
//                    if (strs[k][j] > strs[k][i]) {
//                        flag = 0;
//                        break;
//                    }
//                }
//                if (flag) {
//                    f[i] = max(f[i], f[j]);
//                }
//            }
//            f[i]++;
//        }
//        return n - ranges::max(f);
//    }
//};

//2407. 最长递增子序列 II

//给你一个整数数组 nums 和一个整数 k 。
//找到 nums 中满足以下要求的最长子序列：
//子序列 严格递增
//子序列中相邻元素的差值 不超过 k 。
//请你返回满足上述要求的 最长子序列 的长度。
//子序列 是从一个数组中删除部分元素后，剩余元素不改变顺序得到的数组。

//class Solution {
//    vector<int> max;
//
//    void modify(int o, int l, int r, int i, int val) {
//        if (l == r) {
//            max[o] = val;
//            return;
//        }
//        int m = (l + r) / 2;
//        if (i <= m) modify(o * 2, l, m, i, val);
//        else modify(o * 2 + 1, m + 1, r, i, val);
//        max[o] = std::max(max[o * 2], max[o * 2 + 1]);
//    }
//
//    // 返回区间 [L,R] 内的最大值
//    int query(int o, int l, int r, int L, int R) { // L 和 R 在整个递归过程中均不变，将其大写，视作常量
//        if (L <= l && r <= R) return max[o];
//        int res = 0;
//        int m = (l + r) / 2;
//        if (L <= m) res = query(o * 2, l, m, L, R);
//        if (R > m) res = std::max(res, query(o * 2 + 1, m + 1, r, L, R));
//        return res;
//    }
//
//public:
//    int lengthOfLIS(vector<int>& nums, int k) {
//        int u = *ranges::max_element(nums);
//        max.resize(u * 4);
//        for (int x : nums) {
//            if (x == 1) modify(1, 1, u, 1, 1);
//            else {
//                int res = 1 + query(1, 1, u, std::max(x - k, 1), x - 1);
//                modify(1, 1, u, x, res);
//            }
//        }
//        return max[1];
//    }
//};

//673. 最长递增子序列的个数

//给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
//注意 这个数列必须是 严格 递增的。

//class Solution {
//public:
//    int findNumberOfLIS(vector<int>& nums) {
//        int n = nums.size(), maxLen = 0, ans = 0;
//        vector<int> dp(n), cnt(n);
//        for (int i = 0; i < n; ++i) {
//            dp[i] = 1;
//            cnt[i] = 1;
//            for (int j = 0; j < i; ++j) {
//                if (nums[i] > nums[j]) {
//                    if (dp[j] + 1 > dp[i]) {
//                        dp[i] = dp[j] + 1;
//                        cnt[i] = cnt[j]; // 重置计数
//                    }
//                    else if (dp[j] + 1 == dp[i]) {
//                        cnt[i] += cnt[j];
//                    }
//                }
//            }
//            if (dp[i] > maxLen) {
//                maxLen = dp[i];
//                ans = cnt[i]; // 重置计数
//            }
//            else if (dp[i] == maxLen) {
//                ans += cnt[i];
//            }
//        }
//        return ans;
//    }
//};

//1187. 使数组严格递增

//给你两个整数数组 arr1 和 arr2，返回使 arr1 严格递增所需要的最小「操作」数（可能为 0）。
//每一步「操作」中，你可以分别从 arr1 和 arr2 中各选出一个索引，分别为 i 和 j，0 <= i < arr1.length 和 0 <= j < arr2.length，然后进行赋值运算 arr1[i] = arr2[j]。
//如果无法让 arr1 严格递增，请返回 - 1。

//class Solution {
//public:
//    int makeArrayIncreasing(vector<int>& a, vector<int>& b) {
//        ranges::sort(b); // 为能二分查找，对 b 排序
//        int n = a.size();
//        unordered_map<int, int> memo[n];
//        function<int(int, int)> dfs = [&](int i, int pre) -> int {
//            if (i < 0) return 0;
//            if (auto it = memo[i].find(pre); it != memo[i].end())
//                return it->second; // 之前计算过了
//            // 不替换 a[i]
//            int res = a[i] < pre ? dfs(i - 1, a[i]) : INT_MAX / 2;
//            // 二分查找 b 中小于 pre 的最大数的下标
//            auto k = ranges::lower_bound(b, pre);
//            if (k != b.begin()) // a[i] 替换成小于 pre 的最大数
//                res = min(res, dfs(i - 1, *--k) + 1);
//            return memo[i][pre] = res;
//            };
//        int ans = dfs(n - 1, INT_MAX); // 假设 a[n-1] 右侧有个无穷大的数
//        return ans < INT_MAX / 2 ? ans : -1;
//    }
//};

//1713. 得到子序列的最少操作次数

//给你一个数组 target ，包含若干 互不相同 的整数，以及另一个整数数组 arr ，arr 可能 包含重复元素。
//每一次操作中，你可以在 arr 的任意位置插入任一整数。比方说，如果 arr = [1, 4, 1, 2] ，那么你可以在中间添加 3 得到[1, 4, 3, 1, 2] 。你可以在数组最开始或最后面添加整数。
//请你返回 最少 操作次数，使得 target 成为 arr 的一个子序列。
//一个数组的 子序列 指的是删除原数组的某些元素（可能一个元素都不删除），同时不改变其余元素的相对顺序得到的数组。
//比方说，[2, 7, 4] 是[4, 2, 3, 7, 2, 1, 4] 的子序列（加粗元素），但[2, 4, 2] 不是子序列。

//class Solution {
//public:
//    int minOperations(vector<int>& target, vector<int>& arr) {
//        int n = target.size();
//        unordered_map<int, int> pos;
//        for (int i = 0; i < n; ++i) {
//            pos[target[i]] = i;
//        }
//        vector<int> d;
//        for (int& val : arr) {
//            if (pos.count(val)) {
//                int idx = pos[val];
//                auto it = ranges::lower_bound(d, idx);
//                if (it != d.end()) {
//                    *it = idx;
//                }
//                else {
//                    d.emplace_back(idx);
//                }
//            }
//        }
//        return n - d.size();
//    }
//};

//3288. 最长上升路径的长度

//给你一个长度为 n 的二维整数数组 coordinates 和一个整数 k ，其中 0 <= k < n 。
//coordinates[i] = [xi, yi] 表示二维平面里一个点(xi, yi) 。
//如果一个点序列(x1, y1), (x2, y2), (x3, y3), ..., (xm, ym) 满足以下条件，那么我们称它是一个长度为 m 的 上升序列 ：
//对于所有满足 1 <= i < m 的 i 都有 xi < xi + 1 且 yi < yi + 1 。
//对于所有 1 <= i <= m 的 i 对应的点(xi, yi) 都在给定的坐标数组里。
//请你返回包含坐标 coordinates[k] 的 最长上升路径 的长度。

//class Solution {
//public:
//    int maxPathLength(vector<vector<int>>& coordinates, int k) {
//        int kx = coordinates[k][0], ky = coordinates[k][1];
//        ranges::sort(coordinates, [](const auto& a, const auto& b) {
//            return a[0] < b[0] || a[0] == b[0] && a[1] > b[1];
//            });
//
//        vector<int> g;
//        for (auto& p : coordinates) {
//            int x = p[0], y = p[1];
//            if (x < kx && y < ky || x > kx && y > ky) {
//                auto it = ranges::lower_bound(g, y);
//                if (it != g.end()) {
//                    *it = y;
//                }
//                else {
//                    g.push_back(y);
//                }
//            }
//        }
//        return g.size() + 1;
//    }
//};